class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n == 0) {
            return 1;
        }
    	for (int i = 0; i < n; ++i) {
			int index = A[i];
			while (index >= 1 && index <= n && A[index - 1] != index) {
				int t = A[index - 1];
				A[index - 1] = index;
				index = t;
			}
		}

		int result = 0;
		for (result = 0; result < n; ++result) {
			if (A[result] != result + 1) {
				break;
			}
		}
		return result + 1;
    }
};